//! 排序算法
//! 

/// 二分查找
/// 
/// 入参必须是有序的
/// 

#[allow(dead_code, unreachable_code)]
fn binary_search(to_search: i32, data: Vec<i32>) -> i32 {
    let mut start = 0;
    let mut end = data.len() - 1;

    if to_search < data[start] || to_search > data[end] {
        panic!("not found!");
    }
    
    loop {
        let mid = (start + end) / 2;
        if to_search > data[mid] {
            start = mid;
        } else if to_search < data[mid] {
            end = mid;
        } else {
            return mid as i32;
        }

        if end - start <= 1 {
            panic!("not found!");
        }
    }
} 

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    #[should_panic(expected = "not found!")]
    fn test_binary_search() {
        assert_eq!(0, binary_search(1, vec![1,2,3,4,5,6,7,8,9]));
        assert_eq!(4, binary_search(5, vec![1,2,3,4,5,6,7,8,9]));
        binary_search(0, vec![1,2,3,4,5,6,7,8,9]);
    }
}